package medium

/*
时间复杂度:O(N)
空间复杂度:O(N)

解决：构建一个单调栈，用来存储最终的题目要求的字符串
	为了使字典序足够小，如果遍历过程中当前字符小于栈顶字符，且栈顶字符在当前位置之后还会出现（即在之后位置的出现次数>0），则可以将栈顶元素弹出

关键点:相邻两个字符s[i] s[i+1], 如果s[i+1]<s[i],则应该用s[i+1]替代s[i], 本题中多加了一个限制,就是每个不同的字母必须出现且只出现一次
	也就是说,在用s[i+1]替代s[i]时,必须保证s[i]在i+1位置之后仍会出现(或者说在i+1之后出现次数>0)
*/

func smallestSubsequence(s string) string {
	right := [26]int{}
	for _, v := range s {
		right[v-'a']++
	}
	stack := make([]byte, 0)
	// 记录某个字符是否在stack中出现
	inStack := [26]bool{}

	for i, v := range s {
		// 如果已在stack中出现，则不进行单调栈操作
		if !inStack[v-'a'] {
			for len(stack) > 0 && s[i] < stack[len(stack)-1] {
				last := stack[len(stack)-1]-'a'
				// 如果右边还有该字符,则可以弹出,如果右边没有该字符,则栈顶的该字符是最后一次出现的,不能弹出
				if right[last] == 0 {
					break
				}
				stack = stack[:len(stack)-1]
				// 栈中弹出该元素后,该元素就不存在栈中了
				inStack[last] = false
			}
			stack = append(stack, s[i])
			inStack[v-'a'] = true
		}
		right[v-'a']--
	}
	return string(stack)
}
